import java.util.PriorityQueue;

/**
 * 23. 合并 K 个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/description/
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //1、创建小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        //2、把所有的头结点放进小根堆中
        for(ListNode head : lists)
            if(head != null) heap.offer(head);
        //3、依次拿出小根堆的堆顶元素，合并链表
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(!heap.isEmpty()) {
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;
            if(t.next != null) heap.offer(t.next);
        }
        return ret.next;
    }
}